import java.util.ArrayList;

/**
 * 输入一个字符串,按字典序打印出该字符串中字符的所有排列。
 * 例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
 * 输入描述:
 * 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
 */
public class Solution38 {
    private ArrayList<String> result = new ArrayList<>();

    public ArrayList<String> Permutation(String str) {
        perm(str, 0, str.length() - 1);
        System.out.println(result);
        System.out.println(result.size());
        return result;
    }

    private void perm(String source, int start, int end) {
        // base case
        if (source == null || start >= source.length() || end >= source.length()) {
            return;
        }

        if (start == end) {
            result.add(source);
            return;
        }

        char[] chars = source.toCharArray();
        for (int i = start; i <= end; i++) {
            swap(chars, start, i);
            perm(String.valueOf(chars), start + 1, end);
            swap(chars, start, i);
        }
    }

    private void swap(char[] source, int i, int j) {
        if (source == null || source.length <= i || source.length <= j || i == j) {
            return;
        }

        char temp = source[i];
        source[i] = source[j];
        source[j] = temp;
    }

    private String char2Str(char[] chars) {
        StringBuilder builder = new StringBuilder();
        for (char ch : chars) {
            builder.append(ch);
        }
        return builder.toString();
    }

    public static void main(String[] args) {
        Solution38 solution = new Solution38();
        solution.Permutation("122");
    }
}
